import java.util.Arrays;

public class MergeSort<T extends Comparable<T>> {

    public void mergeSort(T[] data) {
        mergeSort(data, 0, data.length - 1);
    }

    private void mergeSort(T[] data, int left, int right) {
        if (left>=right)
            return ;
        int mid = (left + right)/2;
        mergeSort(data, left, mid);
        mergeSort(data, mid + 1, right);
        merge(data, left, mid, right);
    }

    //合并[left,mid] [mid+1, right]元素
    //形如{1, 3, 8},{2, 6}  => {1, 2, 3, 6, 8}
    //     i         j
    private void merge(T[] data, int left, int mid, int right) {
        if (left>=right)
            return ;
        T[] tem = Arrays.copyOfRange(data, left, right + 1);

        // 初始化，i指向左半部分的起始索引位置left；j指向右半部分起始索引位置mid+1
        int i = left, j = mid + 1;//两个子数组指针
        for (int k = left; k <= right ; k++) {
            if (i > mid) {//左边的数组全部处理完成
                data[k] = tem[j - left];
                j++;
            }else if (j > right){//右边数组全部处理完成
                data[k] = tem[i - left];
                i++;
            }else if (tem[i -left].compareTo(tem[j - left]) < 0) {
                data[k] = tem[i - left];
                i++;
            } else if (tem[i - left].compareTo(tem[j - left]) >= 0) {
                data[k] = tem[j - left];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        Integer[] arr1 = {0, -1, 8, 12, 29, 2, 3, 6, 4, 3, 2, 1, 5, 7, 9};
        new MergeSort<Integer>().mergeSort(arr1);
        System.out.println();
    }
}
